package BFS.review;

import org.junit.Test;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * [精华总结]
 *      1 草稿！
 *      2 广搜 cur下 除了con/re:
 *          其他 核心判断 都写 q.add那里
 *      3 广搜 不用 回溯:
 *          因为 他会 直接 拿 char[i+1] 等价于 回溯的先回再走！
 */
/**
 * 000
 * 100                      010               001               900           090 009
 * 200 110 101 000 090 009  110 020 011 d3    101 011 002 d3    000 910       000 000
 *
 * 只有 草稿 才能明白！ 不要空想！
 *
 */
public class 打开转盘锁752 {
    public int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>();
        for(String d : deadends){
            deadSet.add(d);
        }

        Queue<String> q = new LinkedList<>();
        Set<String> vis = new HashSet<>();
        q.offer("0000");
        vis.add("0000");

        int step = 0;

        while(!q.isEmpty()){
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();

                // vis.add cur下除了 终止if/特  ->  其他条件都写for4中
                if(deadSet.contains(cur)){
                    continue; // 不向下进行 （因为这题要所有情况）
                }
                if(cur.equals(target)){
                    return step;
                }

                for (int j = 0; j < 4; j++) {
                    String up = up(cur,j);
                    String down = down(cur,j);
                    if( ! vis.contains(up)) {
                        q.offer(up); // 广搜 不用 回溯
                        vis.add(up);
                    }
                    if( ! vis.contains(down)) {
                        q.offer(down);
                        vis.add(down);
                    }
                }
            }

            step++;

        }
        return -1; // 出来代表 没有 任何可能 路径
    }

    public String up(String cur, int index){
        char[] chars = cur.toCharArray();
        // 9 向上 0
        if(chars[index] == '9'){
            chars[index] = '0';
        }else {
            chars[index] +=1 ;
        }
        return new String(chars); // String 能传 char[] 构造
    }
    public String down(String cur, int index){
        char[] chars = cur.toCharArray();
        // 0 向下 9
        if(chars[index] == '0'){
            chars[index] = '9';
        }else {
            chars[index] -=1;
        }
        return new String(chars); // String 能传 char[] 构造
    }

    @Test
    public void test() {
        String[] s = new String[]{"0201","0101","0102","1212","2002"};
        String t = "0202";
        System.out.println("RES:" + openLock(s, t));
    }
}
